package year2019.month09;

import java.util.*;

/**
 * 二叉排序树（或称二叉查找树）
 */
public class NumberBSTree {
    class Node{
        Number number;
        Node left;
        Node right;
        Node(Number number){
            this.number = number;
        }

        public Number getNumber() {
            return number;
        }

        public void setNumber(Number number) {
            this.number = number;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    private Node root;
    private int size=0;

    public boolean add(Number number){
        this.root = linkEle(root, number);
        return true;
    }

    public Node linkEle(Node node, Number number){
        Node newNode = new Node(number);
        if (node==null){
            node = newNode;
            size++;
        }else{
            Number nodeNumber = node.number;
            if (number.doubleValue()<nodeNumber.doubleValue()){
                node.left = linkEle(node.left, number);
            } else if (number.doubleValue()>nodeNumber.doubleValue()){
                node.right = linkEle(node.right, number);
            } else; //如果相同，不做任何操作。
        }
        return node;
    }

    public int size(){
        return size;
    }


    public static void main(String[] args){
        Random random = new Random();
        TreeSet treeSet = new TreeSet();
        NumberBSTree numberBSTree = new NumberBSTree();
        for (int i=1; i<=100; i++){
            int nextInt = random.nextInt(100);
            numberBSTree.add(nextInt);
            treeSet.add(nextInt);
        }
        System.out.println("numberBSTree size:"+numberBSTree.size());
        inorderTraversal(numberBSTree.root);
        System.out.println();
        System.out.println("treeSet size:"+treeSet.size());
        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+"、");
        }
    }

    //中序遍历：左子节点-->根节点-->右子节点
    public static void inorderTraversal(Node node){
        if (node!=null){
            inorderTraversal(node.getLeft());
            System.out.print(node.getNumber()+"、");
            inorderTraversal(node.getRight());
        }
    }

}
